﻿// Sequin.Sequences.Sequence
//
// (c) 2011 Arthur Pitman
//
// Part of the Sequin Library
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License (Version 2.1) as published by the Free Software Foundation.
// 
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
// 
// You should have received a copy of the GNU Lesser General Public
// License (Version 2.1) along with this library; if not, write to the 
// Free Software Foundation, Inc., 
// 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA.
// or see <http://www.gnu.org/licenses/>.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Sequin.Sequences
{
	/// <summary>
	/// Represents a (ordered) sequence of elements. Assumes that items within an element are sorted.
	/// </summary>
	public class Sequence
	{
		/// <summary>
		/// The next id to be allocated to a sequence
		/// </summary>
		protected static long nextId;

		/// <summary>
		/// The id of the sequence
		/// </summary>
		public long Id { get; protected set; }

		/// <summary>
		/// The actual sequence
		/// </summary>
		public int[][] Value { get; protected set; }
		
		/// <summary>
		/// The finger print for this <see cref="Sequence"/>, similar to a hash value
		/// </summary>
		public ulong FingerPrint { get; protected set; }
		
		/// <summary>
		/// Initializes a new empty <see cref="Sequence"/> instance
		/// </summary>
		public Sequence()
		{
			Id = nextId;
			nextId++;
			Value = new int[0][];
			FingerPrint = 0;
		}

		static Sequence()
		{
			nextId = 0;
		}


		/// <summary>
		/// Initializes a new <see cref="Sequence"/> from an existing <see cref="Sequence"/>
		/// </summary>
		/// <param name="s">The existing sequence</param>
		public Sequence(Sequence s)
		{
			Id = nextId;
			nextId++;
			Value = s.Value;
			FingerPrint = s.FingerPrint;
		}


		/// <summary>
		/// Initializes a new <see cref="Sequence"/> from an array of elements
		/// </summary>
		/// <param name="value">The array of elements</param>
		public Sequence(int[][] value)
		{
			Id = nextId;
			nextId++;

			Value = value;
			uint fingerPrint = 0;
			foreach (var element in Value)
			{
				foreach (var item in element)
				{
					fingerPrint = fingerPrint | (1u << (item % 64));
				}
			}
			FingerPrint = fingerPrint;
		}

		/// <summary>
		/// Gets the last item in the last element
		/// </summary>
		/// <returns>The last item in the last element or <c>-1</c> if the <see cref="Sequence"/> is empty or the last element is empty</returns>
		public int GetLastItemInLastElement()
		{
			if (Value.Length == 0)
			{
				return -1;
			}
			else
			{
				var lastElement = Value[Value.Length - 1];
				if (lastElement.Length == 0)
					return -1;
				else
					return lastElement[lastElement.Length - 1];
			}
		}

		/// <summary>
		/// Creates a new <see cref="Sequence"/> by appending an additional element
		/// </summary>
		/// <param name="element">The element to append</param>
		/// <returns>The new <see cref="Sequence"/></returns>
		public Sequence ApplySExtension(int[] element)
		{
			int[][] newValue = new int[Value.Length + 1][];
			Value.CopyTo(newValue, 0);
			newValue[Value.Length] = element;
			return new Sequence(newValue);
		}

		/// <summary>
		/// Creates a new <see cref="Sequence"/> by appending an additional element consisting of one item
		/// </summary>
		/// <param name="item">The item to append as a new element</param>
		/// <returns>The new <see cref="Sequence"/></returns>
		public Sequence ApplySExtension(int item)
		{
			int[] element = new int[1];
			element[0] = item;
			return ApplySExtension(element);
		}

		/// <summary>
		/// Creates a new <see cref="Sequence"/> by appending an item to the last element
		/// </summary>
		/// <param name="item">The item to append</param>
		/// <returns>The new <see cref="Sequence"/></returns>
		public Sequence ApplyIExtension(int item)
		{
			if (Value.Length == 0)
			{
				int[][] newValue = new int[1][];
				newValue[0] = new int[1];
				newValue[0][0] = item;
				return new Sequence(newValue);
			}
			else
			{
				int[][] newValue = new int[Value.Length][];
				int i = 0;
				for (i = 0; i < Value.Length - 1; i++)
					newValue[i] = Value[i];

				// add item to last element   
				newValue[i] = InsertIntoArraySorted(Value[i], item);
				return new Sequence(newValue);
			}
		}

		/// <summary>
		/// Determines if this and another <see cref="Sequence"/> are identical
		/// </summary>
		/// <param name="second">The <see cref="Sequence"/> to compare to</param>
		/// <returns><c>true</c> if the two <see cref="Sequence"/> objects are identical, otherwise <c>false</c></returns>
		public bool IsIdentical(Sequence second)
		{
			// first check for finger print and length equality
			if ((FingerPrint != second.FingerPrint) || (second.Value.Length != Value.Length))
				return false;

			// check each element
			for (int i = 0; i < Value.Length; i++)
			{
				if (!IsElementIdentical(Value[i], second.Value[i]))
					return false;
			}
			return true;
		}

		/// <summary>
		/// Determines if this <see cref="Sequence"/> contains another
		/// </summary>
		/// <param name="target">The <see cref="Sequence"/> to examine</param>
		/// <returns><c>true</c> if this <see cref="Sequence"/> contains the other, otherwise <c>false</c></returns>
		public bool Contains(Sequence target)
		{
			if (target.Value.Length > Value.Length)
				return false;

			// check fingerprint containment
			if ((FingerPrint & target.FingerPrint) != target.FingerPrint)
				return false;

			// check each element
			int thisIndex = 0;
			int targetIndex = 0;
			while ((thisIndex < Value.Length) && (targetIndex < target.Value.Length))
			{
				if (ElementContains(Value[thisIndex], target.Value[targetIndex]))
				{
					thisIndex++;
					targetIndex++;
				}
				else
				{
					thisIndex++;
				}
			}
			return (targetIndex >= target.Value.Length);
		}

		/// <summary>
		/// Determines if two elements are identical
		/// </summary>
		/// <param name="firstElement">The first element</param>
		/// <param name="secondElement">The second element</param>
		/// <returns><c>true</c> if the elements are identical, otherwise <c>false</c></returns>
		public static bool IsElementIdentical(int[] firstElement, int[] secondElement)
		{
			// length must be the same
			if (firstElement.Length != secondElement.Length)
				return false;

			// check each item
			// n.b. elements are sorted
			for (int i = 0; i < firstElement.Length; i++)
			{
				if (firstElement[i] != secondElement[i])
					return false;
			}
			return true;
		}

		/// <summary>
		/// Inserts an item into a sorted array of ints
		/// </summary>
		/// <param name="s">The array to insert into</param>
		/// <param name="t">The item to insert</param>
		/// <returns>The new sorted array</returns>
		public static int[] InsertIntoArraySorted(int[] s, int t)
		{
			int[] x = new int[s.Length + 1];
			int i = 0;
			bool toInsert = true;
			foreach (var v in s)
			{
				if ((t < v) && toInsert)
				{
					x[i] = t;
					i++;
					toInsert = false;
				}
				x[i] = v;
				i++;
			}

			if (toInsert)
				x[i] = t;
			return x;
		}

		/// <summary>
		/// Check if element absorbs targetElement
		/// </summary>
		/// <param name="element"></param>
		/// <param name="targetElement"></param>
		/// <returns></returns>
		public static bool ElementContains(int[] element, int[] targetElement)
		{
			if (targetElement.Length > element.Length)
				return false;

			int thisIndex = 0;
			int targetIndex = 0;
			while ((thisIndex < element.Length) && (targetIndex < targetElement.Length))
			{
				if (element[thisIndex] == targetElement[targetIndex])
				{
					thisIndex++;
					targetIndex++;
				}
				else
				{
					thisIndex++;
				}
			}
			return (targetIndex >= targetElement.Length);
		}

		/// <summary>
		/// Projects an element
		/// i.e. checks to see if element A contains element B, and if so, returns all other items in element A
		/// </summary>
		/// <param name="element">The element to project (A)</param>
		/// <param name="projectingElement">The projecting element (B)</param>
		/// <param name="resultElement">The result of the projection</param>
		/// <returns><c>true</c> if a projection exists</returns>
		public static bool ProjectElement(int[] element, int[] projectingElement, out int[] resultElement)
		{
			List<int> projectedItems = new List<int>();

			// check containment
			int thisIndex = 0;
			int targetIndex = 0;
			while ((thisIndex < element.Length) && (targetIndex < projectingElement.Length))
			{
				if (element[thisIndex] == projectingElement[targetIndex])
				{
					thisIndex++;
					targetIndex++;
				}
				else
				{
					projectedItems.Add(element[thisIndex]);
					thisIndex++;
				}
			}

			// add all remaining items to the result
			while (thisIndex < element.Length)
			{
				projectedItems.Add(element[thisIndex]);
				thisIndex++;
			}

			// check if projection was successful
			if (targetIndex >= projectingElement.Length)
			{
				// yes
				resultElement = projectedItems.ToArray();
				return true;
			}
			else
			{
				// no
				resultElement = null;
				return false;
			}
		}

		/// <summary>
		/// Reverses this <see cref="Sequence"/>
		/// </summary>
		/// <returns>The reversed <see cref="Sequence"/></returns>
		public Sequence Reverse()
		{
			// create a new Sequence after flipping it
			return new Sequence(Value.Reverse().ToArray());
		}

		/// <summary>
		/// Calculates the support count of the <see cref="Sequence"/> in a set of <see cref="Sequence"/> objects
		/// </summary>		
		/// <param name="sequenceSet">The set of <see cref="Sequence"/> objects to test</param>
		/// <returns>The support count</returns>
		public int CountSupportIn(IEnumerable<Sequence> sequenceSet)
		{
			// check each sequence for support
			int count = 0;
			foreach (var s in sequenceSet)
			{
				if (s.Contains(this))
					count++;
			}
			return count;
		}
	}
}
